

#include "stl_dlist.h"



/// <summary>
/// 初始化链表
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="c">链表节点的比较函数。在有序插入的时候要用到。</param>
void dlist_init(DList* list, int (*c)(DListNode*, DListNode*))
{
	list->count = 0;
	list->match = c;
	//list->cursor = NULL;
	list->head = NULL;
	list->tail = NULL;
}

/// <summary>
/// 销毁双向链表。链表只记录头尾节点信息，不记录数据，所以只初始化头尾节点即可
/// </summary>
/// <param name="list">链表结构体</param>
void dlist_destroy(DList* list)
{
	list->count = 0;
	//list->cursor = NULL;
	list->head = NULL;
	list->tail = NULL;
}

/// <summary>
/// 按照索引查找节点
/// </summary>
/// <param name="list">链表</param>
/// <param name="index">链表从头开始的索引</param>
/// <returns>节点指针，如果索引超出范围，返回null</returns>
DListNode* dlist_index(DList* list, int index)
{
	if (index >= list->count)return NULL;
	if (index < -list->count)return NULL;

	if (index >= 0) {
		DListNode* node = list->head;
		while (index > 0)
		{
			index--;
			node = node->next;
		}
		return node;
	}
	else
	{
		DListNode* node = list->tail;
		while (index < -1)
		{
			index++;
			node = node->prev;
		}
		return node;
	}
}


/// <summary>
/// 查找节点的索引
/// </summary>
/// <param name="list">链表</param>
/// <param name="node">节点</param>
/// <returns>节点的索引，索引从0开始计数，如果节点不在链表上，返回-1</returns>
int dlist_index_of(DList* list, DListNode* node)
{
	int i = 0;
	DListNode* cursor;
	for (cursor = list->head; cursor != NULL; cursor = cursor->next)
	{
		if (cursor == node) {
			return i;
		}
		i++;
	}
	return -1;
}


/// <summary>
/// 在 element 后面插入一个新元素
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="element">定位的节点</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否插入成功，如果element是合法的节点，是可以成功插入的</returns>
bool dlist_ins_next(DList* list, DListNode* element, DListNode* new_element)
{

	if (element == NULL) {
		// 如果不是空表， element 又是 NULL，就无法插入了。 否则，空表，element可以是null
		if (list->count != 0)
			return false;
	}

	// 插入元素到链表
	if (list->count == 0) {
		// 处理空双向链表
		list->head = new_element;
		list->head->prev = NULL;
		list->head->next = NULL;
		list->tail = new_element;
	}
	else {
		// 处理非空双向链表
		new_element->next = element->next;
		new_element->prev = element;
		if (element->next == NULL) {
			list->tail = new_element;
		}
		else {
			element->next->prev = new_element;
		}
		element->next = new_element;

	}
	// 更新链表的 数量
	list->count++;
	return true;
}

/// <summary>
/// 在 element 前面插入一个新元素
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="element">定位的节点</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否插入成功，如果element是合法的节点，是可以成功插入的</returns>
bool dlist_ins_prev(DList* list, DListNode* element, DListNode* new_element)
{
	if (element == NULL) {
		// 如果不是空表， element 又是 NULL，就无法插入了。 否则，空表，element可以是null
		if (list->count != 0)
			return false;
	}

	if (list->count == 0) {
		// 处理空双向链表
		list->head = new_element;
		list->head->prev = NULL;
		list->head->next = NULL;
		list->tail = new_element;
	}
	else {
		// 处理非空双向链表
		new_element->next = element;
		new_element->prev = element->prev;
		if (element->prev == NULL) {
			list->head = new_element;
		}
		else {
			element->prev->next = new_element;
		}
		element->prev = new_element;
	}
	// 更新链表的 数量
	list->count++;
	return true;
}

/// <summary>
/// 在双向链表 中移除 element 元素
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="element">移除的节点</param>
/// <returns>是否操作成功。如果element是合法的节点，是可以操作成功的</returns>
bool dlist_remove(DList* list, DListNode* element)
{
	// 禁止 element 为空
	if (element == NULL) return false;

	if (element == list->head) {
		// 处理删除头部元素
		list->head = element->next;
		if (list->head == NULL) {  //说明表中只有一个元素。
			list->tail = NULL;
		}
		else {
			element->next->prev = NULL;
			list->head->prev = NULL; //头结点没有上一个结点。
		}
	}
	else {
		// 处理删除非头部元素，说明element前面至少有一个元素
		element->prev->next = element->next;
		if (element->next == NULL) { //说明删除的element是尾结点。
			list->tail = element->prev;
			list->tail->next = NULL; //尾结点没有下一个结点
		}
		else {
			element->next->prev = element->prev;
		}
	}
	// 更新链表的 数量
	list->count--;
	return true;
}

/// <summary>
/// 在双向链表尾部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool dlist_push_back(DList* list, DListNode* new_element)
{
	if (list->count == 0) {
		// 处理空双向链表
		list->head = new_element;
		list->tail = new_element;
		list->head->prev = NULL;
		list->head->next = NULL;
	}
	else {
		// 处理非空双向链表
		new_element->next = NULL;
		new_element->prev = list->tail;
		list->tail->next = new_element;
		list->tail = new_element;
	}
	// 更新链表的 数量
	list->count++;
	return true;
}

/// <summary>
/// 在双向链表头部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool dlist_push_front(DList* list, DListNode* new_element)
{
	if (list->count == 0) {
		// 处理空双向链表
		list->head = new_element;
		list->tail = new_element;
		list->head->prev = NULL;
		list->head->next = NULL;
	}
	else {
		// 处理非空双向链表
		new_element->next = list->head;
		new_element->prev = NULL;
		list->head->prev = new_element;

		list->head = new_element;
	}
	// 更新链表的 数量
	list->count++;
	return true;
}

/// <summary>
/// 在双向链表尾部弹出一个数据
/// </summary>
/// <param name="list">链表结构体</param>
/// <returns>是否操作成功</returns>
bool dlist_pop_back(DList* list)
{
	if (list->count == 0) {
		return false;
	}
	if (list->count == 1) {
		dlist_destroy(list);
		return true;
	}
	else {
		list->tail = list->tail->prev;
		list->tail->next = NULL;
		// 更新链表的 数量
		list->count--;
		return true;
	}
}

/// <summary>
/// 在双向链表头部弹出一个数据
/// </summary>
/// <param name="list">链表结构体</param>
/// <returns>是否操作成功</returns>
bool dlist_pop_front(DList* list)
{
	if (list->count == 0) {
		return false;
	}
	if (list->count == 1) {
		dlist_destroy(list);
		return true;
	}
	else {
		list->head = list->head->next;
		list->head->prev = NULL;
		// 更新链表的 数量
		list->count--;
		return true;
	}
}


/// <summary>
/// 按序插入节点。按照从小到大的顺序插入。如果所有元素都是按序插入的，整个链表就是有序的。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="new_element">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool dlist_ins_orderly(DList* list, DListNode* new_element)
{
	if (new_element == NULL) {
		return false;
	}
	DListNode* cursor;
	for (cursor = list->head; cursor != NULL; cursor = cursor->next)
	{
		if (list->match(cursor, new_element) != -1) {
			dlist_ins_prev(list, cursor, new_element);
			return true;
		}
	}
	dlist_push_back(list, new_element);
	return true;
}
//


// 测试dlist


typedef struct  data_
{
	DListNode node;
	char c0;
	char c1;
	int a;
	char c2;
	float b;
	char c3;
}Data;

int matchsdata(DListNode* key1, DListNode* key2)  //key1>key2返回1，key1<key2返回-1,key1=key2返回0.
{
	Data* d1, * d2;
	d1 = container_of(key1, Data, node);
	d2 = container_of(key2, Data, node);
	if (d1->a > d2->a)return 1;
	else if (d1->a < d2->a)return -1;
	else return 0;
}

void printslist(DList list)
{
	DListNode* list_cursor;
	printfs("  positive order: ");
	for (list_cursor = list.head; list_cursor != NULL; list_cursor = list_cursor->next)
	{
		printfs(" %d, ", (container_of(list_cursor, Data, node))->a);
	}
	printfs("  reverse order: ");
	for (list_cursor = list.tail; list_cursor != NULL; list_cursor = list_cursor->prev)
	{
		printfs(" %d, ", (container_of(list_cursor, Data, node))->a);
	}
	printfs("  \r\n");

}

void test_dlist()
{
	DList list;
	dlist_init(&list, matchsdata);
	//
 
	printfs(  " inta[] =  5,4,1,2,3  \r\n");
	int inta[5] = { 5,4,1,2,3 };
	Data ints[5];
	for (int i = 0; i < 5; i++) {
		ints[i].a = inta[i];
	}

	printfs(  "list.head   dlist_ins_next \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_ins_next(&list, list.head, &(ints[i].node));
	}
	printslist(list);
	printfs(  " list.head   dlist_remove \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_remove(&list, list.head);
		printslist(list);
	}

	printfs(  "list.head  dlist_ins_prev \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_ins_prev(&list, list.head, &(ints[i].node));
	}
	printslist(list);
	printfs(  "list.tail  dlist_remove \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_remove(&list, list.tail);
		printslist(list);
	}

	printfs(  "list.tail  dlist_ins_next \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_ins_next(&list, list.tail, &(ints[i].node));
	}
	printslist(list);
	dlist_destroy(&list);

	printfs(  "list.tail   dlist_ins_prev \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_ins_prev(&list, list.tail, &(ints[i].node));
	}
	printslist(list);
	dlist_destroy(&list);


	printfs(  "dlist_push_front \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_push_front(&list, &(ints[i].node));
	}
	printslist(list);

	printfs(  "dlist_pop_back \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_pop_back(&list);
		printslist(list);
	}



	dlist_destroy(&list);
	printfs(  "dlist_push_back \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_push_back(&list, &(ints[i].node));
	}
	printslist(list);

	printfs(  "dlist_pop_front \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_pop_front(&list);
		printslist(list);
	}
	dlist_destroy(&list);

	//测试排序，按序插入。
	printfs(  "test dlist_ins_orderly \r\n");
	for (int i = 0; i < 5; i++) {
		dlist_ins_orderly(&list, &(ints[i].node));
	}
	printslist(list);


	printfs("test dlist_index \r\n");
	for (int i = 0; i < 5; i++) {
		DListNode* list_cursor = dlist_index(&list, i);
		printfs(" %d, ", (container_of(list_cursor, Data, node))->a); 
	}
	for (int i = 0; i < 5; i++) {
		DListNode* list_cursor = dlist_index(&list, i);
		printfs(" index = %d ", dlist_index_of(&list, list_cursor));
	}

	printfs(  " test finish  \r\n ");

}











